package day02;

// 构建二叉树

import java.util.*;
/**
 * Definition for binary tree
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}

public class Main2 {
    // 这里使用的是： 闭区间！
    private static TreeNode reConstructBinaryTree(int[] pre,int pre_start,int pre_end,int[] vin,int vin_start,int vin_end) {
        // 判断条件:一定要存在，否则编译失败！
        if(pre_start>pre_end || vin_start>vin_end) {
            return null;
        }
        // 根结点:前序遍历的第一个元素就是
        TreeNode root = new TreeNode(pre[pre_start]);
        // 然后再中序遍历中找到根结点位置
        // 注意开始遍历的位置！
        for(int i=vin_start; i<=vin_end; i++) {
            if(root.val == vin[i]) {
                // 找到了根结点，然后开始构建左右子树
                // 一定要注意参数！！
                // 左子树
                root.left = reConstructBinaryTree(pre,pre_start+1,pre_start+1+i-vin_start-1,vin,vin_start,i-1);
                // 右子树
                root.right = reConstructBinaryTree(pre,pre_start+1+i-vin_start,pre_end,vin,i+1,vin_end);

                break;
            }
        }

        return root;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        // 首先进行判断
        if(pre==null || vin==null || pre.length!=vin.length) {
            return null;
        }

        // 其实关键就是：找到根结点以及左右子树
        return reConstructBinaryTree(pre,0,pre.length-1,vin,0,vin.length-1);
    }


    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] vin = {4,7,2,1,5,3,8,6};
        Main2 main2 = new Main2();
        TreeNode root = main2.reConstructBinaryTree(pre,vin);
        // 打印要使用递归方法
    }
}
